package com.ddf.datastructure.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * 虚拟的将一个无序数组当成两个部分，一部分是有序的，一部分是无序的，其实还是一个数组，只是概念上这样区分
 * 比如数组长度为n
 * 那么第一个元素[0]就是有序的,剩余的[1]到[n-1]都是无序的，然后循环无序元素[1]，然后拿未排序的[1]和已排序的[1]之前的所有元素
 * 进行比较大小（全部按照从小到大来说），如果[1]的元素小于[0]的元素，那么[1]的元素就要放到[0]位置元素的前面，原[0]位置的元素就要放到[1]上，
 * 然后将当前[1]的元素放到[0]元素上;
 *
 * 以上步骤循环，需要注意的是，无序的元素放到有序的位置时，要一直循环找到最合适它的位置，找到比当前元素大的时候，还要继续往前找，一致找到数组的[0]角标
 * 这样才能确定当前无序元素的最终位置
 *
 * 可以看到，如果我们按照从小到大的顺序排列，如果小的元素都堆积到后面，那么移位的次数是相当多的
 *
 * 最差时间复杂度O(n²), 最好时间复杂度O(n)
 *
 *
 *
 * @author dongfang.ding
 * @date 2019/6/27 13:35
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {20, 19, 18, 17, 16, 15, 14, 13};
        int[] sort = sort(arr);

        System.out.println("排序前： " + Arrays.toString(arr));
        System.out.println("排序后： " + Arrays.toString(sort));
    }

    public static int[] sort(int[] arr) {
        // 数组复制，不改变原数组内容
        int[] dest = Arrays.copyOf(arr, arr.length);

        int insertVal = 0;
        // 第一个元素是有序的，所以第一个不用排，少循环一次就好
        for (int i = 1; i < dest.length; i++) {
            // 从[1]开始每次循环，记录每个位置待插入的元素，这个位置的元素会与该元素前面的所有元素进行比较，找到它合适的位置
            insertVal = dest[i];
            // 临时变量
            int j = i;
            // 将当前元素与该元素之前已排序的元素一个个比较
            while (j > 0 && insertVal < dest[j - 1]) {
                // 如果该元素比之前的元素小，那么将前一个元素后移（可以看到是通过将前一个元素的值覆盖到后面那个角标的位置）
                // 如20 19，当前比较的是19， 19小于它的前一位20，所以应该将20后移，给19腾位置，但是后移的操作不好操作，
                // 于是用变量先将当前要插入的19保存起来，然后将19的位置用20覆盖，这样数据就变成了了20 20，然后循环结束，找到了
                // 19要插入的位置，就是（对应j--,也就是1-1=0），所以19放到0的位置，数组就变成了19 20
                dest[j] = dest[j - 1];
                j --;

            }
            if (j != i) {
                dest[j] = insertVal;
            }
        }
        return dest;
    }
}
